package com.Jancode.leetcode;

import java.util.ArrayList;
import java.util.List;

public class AllPathsFromSourceToTarget {

    class Solution {
        private List<Integer> route;          // the candidate routes for current.
        private List<List<Integer>> paths;    // the whole flexible paths.

        public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
            int target = graph.length - 1;  // the target vertex
            paths = new ArrayList<>();
            route = new ArrayList<>();

            dfs(graph, 0, target);

            return paths;
        }

        private void dfs(int[][] g, int src, final int dst) {
            route.add(src);

            // check whether now we have arrived the target vertex. 
            if(src == dst) {
                // now the route is ok.
                List<Integer> path = new ArrayList<>(route);
                paths.add(path);

                // backtracking before returning
                route.remove((Integer) src); 
                return;              
            }

            for(int adj : g[src]) {
                if(!route.contains(adj)) {
                    dfs(g, adj, dst);
                    route.remove((Integer) adj);
                }
            }
        }
    }

}